2.4 SOR 收敛

定理 i-2-4（充分条件） $0 < \omega \le 1$ $\bm A$ $\bm A \bm x = \bm b$ 的 SOR 迭代法收敛.

证明

$\wt{\bm B}$ $\Norm{\wt{\bm B}} = \wt q < 1$ . 将迭代方程拆分为：

{\begin{cases} {\tilde{x}}^{(k + 1)} = \tilde{B} x^{(k)} + \tilde{f}, \\ x^{(k + 1)} = (1 - ω) x^{(k)} + ω {\tilde{x}}^{(k + 1)} . \end{cases}

$\bm x^{(k)}$ $\wt{\bm x}^{(k)}$ . 于是

{\begin{cases} {\tilde{x}}^{(k + 1)} = \tilde{B} x^{(k)} + \tilde{f}, \\ x^{*} = \tilde{B} x^{*} + \tilde{f} . \end{cases} \Rightarrow \begin{aligned} ‖ {\tilde{x}}^{(k + 1)} - x^{*} ‖ & \leq ‖ \tilde{B} ‖ ‖ x^{(k)} - x^{*} ‖ = \tilde{q} ‖ ε^{(k)} ‖ . \end{aligned}

该式本身不构成地推关系，但是由此有

\begin{aligned} ‖ ε^{(k + 1)} ‖ & = ‖ (1 - ω) x^{(k)} + ω {\tilde{x}}^{(k + 1)} - x^{*} ‖ \\ = ‖ (1 - ω) ε^{(k)} + ω ({\tilde{x}}^{(k + 1)} - x^{*}) ‖ \\ \leq | 1 - ω | \cdot ‖ ε^{(k)} ‖ + | ω | \cdot \tilde{q} \cdot ‖ x^{(k)} - x^{*} ‖ \\ = (| 1 - ω | + | ω | \tilde{q}) ‖ ε^{(k)} ‖ \\ \leq {(| 1 - ω | + | ω | \tilde{q})}^{k + 1} ‖ ε (0) ‖, \end{aligned}

$\vqty{1 - \omega} + \vqty{\omega} \wt q < 1$ ，故 SOR 迭代法收敛.

备注